package com.example.demo.arithmetic.algorithm.greedy.bag;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 贪心算出来的并不对
 * 0 1背包问题,要么拿 要么不拿，不能只拿一部分，这是和分数背包最大的区别
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        BagProblem.Item[] items = new BagProblem.Item[]{
                new BagProblem.Item(0, 1, 1_000_000),
                new BagProblem.Item(1, 4, 1600),
                new BagProblem.Item(2, 8, 2400),
                new BagProblem.Item(3, 5, 30),
        };
        // 算出来的并不对
        System.out.println(new KnapsackProblem().maxValue(items, 10));
    }

    public int maxValue(BagProblem.Item[] items, int targetWight) {
        // 优先选单价最贵的 -item.price就是降序了 太骚了实在是！！
        Arrays.sort(items, Comparator.comparing(item -> -item.price));
        //        System.out.println(Arrays.toString(items));
        int count = 0;
        for (BagProblem.Item item : items) {
            if (item.weight > targetWight) { // 只拿一部分
                //                count += targetWight * item.price;
                //                break;
            } else {
                // 你要的全拿走
                targetWight -= item.weight;
                count += item.sum;
            }
        }
        return count;
    }
}

